package com.sgg.datastructure.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node huffmanTree = createHuffmanTree(arr);
        huffmanTree.preOrderPrint();
    }

    /**
     * ● 从小到大进行排序,将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
     * ● 取出根节点权值最小的两颗二叉树
     * ● 组成一颗新的二叉树,该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
     * ● 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
     */
    public static Node createHuffmanTree(int[] arr) {
        List<Node> list = new ArrayList<>();
        for (int i : arr) {
            list.add(new Node(i));
        }
        while (list.size() > 1) {
            doFun(list);
        }
        return list.get(0);
    }

    public static void doFun(List<Node> list) {
        Collections.sort(list);
        Node node0 = list.get(0);
        Node node1 = list.get(1);
        Node newNode = new Node(node0.value + node1.value);
        newNode.left = node0;
        newNode.right = node1;
        list.remove(node0);
        list.remove(node1);
        list.add(newNode);
    }
}
